package leetcode.图.拓扑排序;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/8/6 23:44
 * @description：https://leetcode-cn.com/problems/minimum-height-trees/
 */
public class 最小高度树 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.findMinHeightTrees(6, new int[][]{{0, 3}, {1, 3}, {2, 3}, {4, 3}, {5, 4}}));
    }

    class Solution {
        List<List<Integer>> edges_list;
        int[] inDeg;
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            List<Integer> ans = new ArrayList<>();
            if (n == 1) {
                ans.add(0);
                return ans;
            }
            inDeg = new int[n];
            edges_list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                edges_list.add(new ArrayList<>());
            }
            for (int[] edge : edges) {
                edges_list.get(edge[1]).add(edge[0]);
                edges_list.get(edge[0]).add(edge[1]);
                inDeg[edge[0]]++;
                inDeg[edge[1]]++;
            }
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < inDeg.length; i++) {
                if (inDeg[i] == 1) {
                    queue.offer(i);
                }
            }
            while (!queue.isEmpty()) {
                ans = new ArrayList<>();
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Integer cur = queue.poll();
                    ans.add(cur);
                    for (Integer in : edges_list.get(cur)) {
                        if (--inDeg[in] == 1) {
                            queue.offer(in);
                        }
                    }
                }
            }
            return ans;
        }
    }
}
